#include<iostream>
using namespace std;
#include<string>

struct TNode
{
	int _val;
	TNode* _left;
	TNode* _right;
	TNode(int v)
		:_val(v)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

TNode* Create(int* a, int* pi)
{
	TNode* root = nullptr;
	if (a[*pi] != -1)
	{
		root = new TNode(a[*pi]);
		(*pi)++;
		root->_left = Create(a, pi);
		root->_right = Create(a, pi);
	}
	else
	{
		(*pi)++;
		return nullptr;
	}
	return root;
}

void Insert(TNode* root, int val)
{
	if (val < root->_val)
	{
		if(root->_left)
			Insert(root->_left, val);
		else
		{
			TNode* tmp = new TNode(val);
			root->_left = tmp;
		}
	}
	else
	{
		if(root->_right)
			Insert(root->_right, val);
		else
		{
			TNode* tmp = new TNode(val);
			root->_right = tmp;
		}
	}

}
void Pre(TNode* root)
{
	if(root)
	{
		cout << root->_val << ' ';
		Pre(root->_left);
		Pre(root->_right);
	}
}
void In(TNode* root)
{
	if (root)
	{
		In(root->_left);
		cout << root->_val << ' ';
		In(root->_right);
	}
}
int main()
{
	int a[] = { 8,3,1,-1,-1,6,4,-1,-1,7,-1,-1,10,-1,14,13,-1,-1,-1 };
	int i = 0;
	TNode* root = Create(a, &i);
	In(root);
	cout << endl;

	Insert(root, 16);
	In(root);
	cout << endl;

	Insert(root, 0);
	In(root);
	cout << endl;
	Insert(root, 2);
	In(root);
	cout << endl;
	return 0;
}